1. Field of the Invention
The present invention relates to an apparatus for automatically generating a movement path for a mobile object. More particularly, the present invention relates to a path generator utilizing artificial potential based on positional relationship among objects in an object space and determination of a local minimum.
2. Description of the Related Art
One of known techniques for mobile object navigation is the artificial potential method as is describes in Non-patent Document 1. This method forms a potential field in an object space in which navigation is to be performed and determines an overall path to a destination point based on the gradient of the potential field. A movement path is generated by repeating a search for a minimum potential point in the vicinity of the current position. The artificial potential method is superior to other conventional techniques such as graph search in that it can automatically and flexibly generate a path in an object space.
However, in the artificial potential method, in principle, a search for a movement path may converge to a local minimum halfway and a movement path to the ultimate destination point may not be generated for certain structures of potential field of the object space in which navigation is performed.
In order to avoid such a local minimum problem, a path planning method utilizing Laplace potential is also known as can be seen in Non-patent Document 2. The Laplace potential method sets a plurality of cells for calculating potentials as a grid in an object space in which navigation is performed, and performs a calculation using the Laplace differential equation for each of the cells.
However, in the Laplace potential method, there will be a single minimum point in an entire potential field and calculation needs be repeated until the minimum point corresponds with the destination point. Thus, calculation takes a significantly long time depending on the structure of the object space. Thus, rapid path planning, guidance of a mobile object, and change of a path can hardly be performed.